import java.util.HashSet;
import java.util.List;

public class demo1 {
    class Solution {
        public boolean wordBreak(String s, List<String> wordDict) {
            int n=s.length();
            HashSet<String> set;
            set = new HashSet(wordDict);
            boolean []dp=new boolean[n+1];
            s=" "+s; //处理下标映射关系
            dp[0]=true;
            for(int i=1;i<=n;i++){
                for(int j=i;j>=1;j--){
                    if(dp[j-1]&&set.contains(s.substring(j,i+1))){
                        dp[i]=true;
                    }
                }
            }
            return dp[n];
        }
    }
}
